package com.zyk.leetcode;

import java.util.*;

/**
 * @author zhangsan
 * @date 2021/4/3 16:08
 */
public class J59 {


    static class MaxQueue {

        /** 双端队列存放元素, 右边进,左边出 */
        Deque<Integer> elements;
        /** 记录每一步的最大值 */
        List<Integer> maxList;

        public MaxQueue() {
            elements = new ArrayDeque<>();
            maxList = new LinkedList<>();
        }

        public int max_value() {
            if(!maxList.isEmpty()) {
                return maxList.get(0);
            }
            return -1;
        }

        public void push_back(int value) {
            elements.addLast(value);   // 右边进,左边出
            maxList.add(value);
            for (int i = maxList.size()-2; i >= 0; i--) {
                if(value > maxList.get(i)) {
                    maxList.set(i, value);
                }else {
                    break;
                }
            }
        }

        public int pop_front() {
            if(elements.size() > 0) {
                int v = elements.removeFirst();
                maxList.remove(0);
                return v;
            }
            return -1;
        }
    }

    // for test
    public static void main(String[] args) {
        // 输入:
        //["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
        //[[],[1],[2],[],[],[]]
        //输出: [null,null,null,2,1,2]


        MaxQueue maxQueue = new MaxQueue();
        maxQueue.push_back(1);
        maxQueue.push_back(2);
        System.out.println(maxQueue.max_value());
        System.out.println(maxQueue.pop_front());
        System.out.println(maxQueue.max_value());
    }

}
